package com.dexter.year2023.charpter8_tree_hot_problems.level1.topic1_1双指针;

import com.dexter.year2023.charpter6_tree_level_travel.level1.TreeNode;

/**
 * LeetCode 101. 对称二叉树
 * https://leetcode.cn/problems/symmetric-tree/
 * <p>
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 示例 2：
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * <p>
 * 提示：
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * <p>
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 *
 * @author Dexter
 */
public class LC101IsSymmetric {
    public static void main(String[] args) {
        // 构造对称的二叉树
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(9);
        node.right.right = new TreeNode(7);
        node.right.left = new TreeNode(15);

        node.left.right = new TreeNode(15);
        node.left.left = new TreeNode(7);

        System.out.println("是否为对称二叉树：" + (isSymmetric(node) ? "是" : "否"));
    }

    /**
     * 法1：递归法 - 时间击败100% 的Java用户，内存击败27.78% 的Java用户
     */
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }

    public static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return check(p.left, q.right) && check(p.right, q.left);
    }
}
